package com.agile.leetcode.array.sum.sort;

import java.util.Arrays;

/**
 * 基数排序
 * @Author ChenZhangKun
 * @Date 2020/7/31 14:49
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr={4,25,6,48,22,899,41,6,3,59,4,6,2,55,41,78,88,1};
        int[] ints = radixSort(arr);
        System.out.println(Arrays.toString(ints));
    }
    public static int[] radixSort(int[] arr){
        // 找出最大的数
        int max=Integer.MIN_VALUE;
        for (int i : arr) {
            if (i>max){
                max=i;
            }
        }
        // 拿到max位数
        int length=(max+"").length();
        // 创建二维数组，桶数
        int[][] bucket=new int[10][arr.length];
        // 一维数组存放桶里面的个数
        int[] bucketElementCount=new int[10];
        for (int n = 1; n <= length; n++) {
            //
            int m=(int)Math.pow(10,n-1);
            for (int i = 0; i < arr.length; i++) {
                int digit=arr[i]/m%10;
                // 放入桶中
                bucket[digit][bucketElementCount[digit]]=arr[i];
                bucketElementCount[digit]++;
            }
            int index=0;
            for (int i = 0; i < bucket.length; i++) {
                if (bucketElementCount[i]!=0){
                    for (int i1 = 0; i1 < bucketElementCount[i]; i1++) {
                        arr[index]=bucket[i][i1];
                        index++;
                    }
                }
                bucketElementCount[i]=0;
            }
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }
}
